package leetcode.editor.cn.q1_300.q100;

import leetcode.editor.cn.util.list.singly.ListNode;
import leetcode.editor.cn.util.list.singly.ListUtil;

/**
 * @author qidi
 * @date 2022-01-18 09:16:43
 */
class Q0147_InsertionSortList {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public ListNode insertionSortList(ListNode head) {
            if (head == null || head.next == null) return head;
            // 新的头
            ListNode h = head;
            // 新排序好链表的尾
            ListNode hTail = head;
            // 当前遍历到需要排序的节点
            ListNode cur = head.next;
            while (cur != null) {
                ListNode tmp = cur.next;
                if (cur.val < hTail.val) {

                    cur.next = null;

                    ListNode cc = h;
                    ListNode pre = null;
                    while (cc != null && cc != cur && cc.val < cur.val) {
                        pre = cc;
                        cc = cc.next;
                    }

                    if (cc == cur) {
                        hTail = cc;
                    } else {
                        cur.next = cc;
                    }
                    if (pre != null) {
                        pre.next = cur;
                    } else {
                        h = cur;
                    }
                    hTail.next = tmp;
                } else {
                    hTail = cur;
                }

                cur = tmp;
            }
            return h;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0147_InsertionSortList().new Solution();
        ListUtil util = ListUtil.getInstance();
        System.out.println(solution.insertionSortList(null));
        System.out.println(solution.insertionSortList(util.generateFromArray(4, 2, 1, 3)));
        System.out.println(solution.insertionSortList(util.generateFromArray(4, 3, 2, 1, -8)));
        System.out.println(solution.insertionSortList(util.generateFromArray(-1, 5, 3, 4, 0)));
    }
}